package com.markus.code.newcode;

import com.markus.basic.Java基础.重写与重载.A;

import java.util.ArrayList;
import java.util.List;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/7 11:09
 * todo:
 */
public class MergeKLists {
    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists == null || lists.size() == 0){
            return null;
        }
        if (lists.size() == 1){
            return lists.get(0);
        }
        if (lists.size() % 2 != 0){
            lists.add(null);
        }
        ArrayList<ListNode> sum = new ArrayList<>();
        for (int i=0;i<lists.size()-1;i+=2){
            sum.add(merge(lists.get(i),lists.get(i+1)));
        }
        return mergeKLists(sum);
    }
    private ListNode merge(ListNode node1,ListNode node2){
        ListNode head = new ListNode(-1);
        ListNode node = head;
        while(node1 != null && node2 != null){
            if (node1.val <= node2.val){
                node.next = node1;
                node1 = node1.next;
            }else{
                node.next = node2;
                node2 = node2.next;
            }
            node = node.next;
        }
        if (node1 != null){
            node.next = node1;
        }
        if (node2 != null){
            node.next = node2;
        }
        return head.next;
    }

    private void printListNode(ListNode root){
        while(root != null){
            System.out.print(root.val + " ");
            root = root.next;
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(2);
        ListNode node2 = null;
        ListNode node3 = new ListNode(-1);
        ArrayList<ListNode> list = new ArrayList<>();
        list.add(node1);
        list.add(node2);
        list.add(node3);
        MergeKLists demo = new MergeKLists();
        ListNode node = demo.mergeKLists(list);
        demo.printListNode(node);
    }
}
